#pragma once
#include<iostream>
#include<assert.h>
#include<initializer_list>
using namespace std;

namespace x {
	template<class T>
	struct list_node
	{
		T val;
		struct list_node* Next;
		struct list_node* Prev;
		list_node(const T& val = T())
			:val(val)
			, Next(nullptr)
			, Prev(nullptr)
		{}

		list_node(list_node& node)
		{
			val = node->val;
			Next = node->Next;
			Prev = node->Prev;
		}

	};

	template<class T,class Ref,class Ptr>
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator<T,Ref,Ptr> iterator;
		Node* _node;
		list_iterator(Node* node)
			:_node(node)
		{}

		Ref operator*()
		{
			return _node->val;
		}

		Ptr operator->()
		{
			return &_node->val;
		}

		iterator& operator++()
		{
			_node = _node->Next;
			return *this;
		}

		iterator operator++(int)
		{
			iterator ret(*this);
			_node = _node->Next;
			return ret;
		}

		iterator& operator--()
		{
			_node = _node -> Prev;
			return *this;
		}

		iterator operator--(int)
		{
			iterator ret(*this);
			_node = _node->Prev;
			return ret;
		}

		bool operator!=(const iterator& s)
		{
			return _node != s._node;
		}

		bool operator==(const iterator& s)
		{
			return _node == s._node;
		}

	};

	template<class T>
	class list
	{
	public:
		typedef list_node<T> Node;
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T,const T&,const T*> const_iterator;
		list()
		{
			_head = new Node;
			_head->Next = _head;
			_head->Prev = _head;
			_size = 0;
		}

		list(initializer_list<T> il)
		{
			emptyinit();
			for (auto e : il)
			{
				push_back(e);
			}
		}

		void swap(list<T>& lt)
		{
			std::swap(_head,lt._head);
			std::swap(_size,lt._size);
		}

		void emptyinit()
		{
			_head = new Node;
			_head->Next = _head;
			_head->Prev = _head;
			_size = 0;
		}

		list(const list<T>& lt)
		{
			emptyinit();
			for (auto e : lt)
			{
				push_back(e);
			}
		}

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		iterator begin()
		{
			return _head->Next;
		}
		const_iterator begin()const
		{
			return _head->Next;
		}

		iterator end()
		{
			return _head;
		}

		const_iterator end()const
		{
			return _head;
		}

		void push_back(const T& x=T())
		{
			insert(end(), x);
			++_size;
		}

		void push_front(const T& x = T())
		{
			insert(begin(), x);
			++_size;
		}

		void insert(iterator pos,const T& x = T())
		{
			Node* _pos = pos._node;
			Node* prev = _pos->Prev;

			Node* new_node = new Node(x);

			new_node->Prev = prev;
			new_node->Next = _pos;
			prev->Next = new_node;
			_pos->Prev = new_node;
			++_size;
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* _pos = pos._node;
			Node* prev = _pos->Prev;
			Node* next = _pos->Next;

			prev->Next = next;
			next->Prev = prev;
			return next;
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				it=erase(it);
			}
		}

		bool empty()const
		{
			return size() == 0;
		}

		size_t size()
		{
			return _size;
		}

	private:
		Node* _head;
		size_t _size;
	};

	template<class container>
	void print_container(const container& con)
	{
		for (auto e : con)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_list();
	void test_list1();
	void test_list2();
	void test_list3();
}
